import java.util.Arrays;

public class Solution685 {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n=edges.length;
        int[] b=new int[n+1];
        int size=n;
        for (int i=0;i<=n;i++){
            b[i]=i;
        }
        int p=-1;
        int[] du=new int[n+1];
        int[] ans=new int[2];
        for (int[] edge : edges) {
            int x=find(b,edge[0]);
            int y=find(b,edge[1]);
            if (du[edge[1]]==1){
                p=edge[1];
            }
            if (x!=y && du[edge[1]]==0){
                du[edge[1]]++;
                size--;
                b[x]=y;
            }else{
                ans=edge;
            }
        }
        //如果size为1，表示合并成功，ans正是我们想要的结果
        if (size==1) {
            return ans;
        }else{//否则，说明我们取错边了，一定存在某个点有两个父节点，且有一个父节点和这个节点不在一个并查集中
            //保留不在同一并查集中的父节点->节点的这条边，弃置在同一并查集中父节点->节点的另一条边。
            for (int i=n-1;i>=0;i--){
                if (edges[i][1]==p && find(b,edges[i][0])==find(b,edges[i][1])){
                    return edges[i];
                }
            }
        }
        return null;
    }

    int find(int[] b,int t){
        while (b[t]!=t){
            t=b[t];
        }
        return t;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution685().findRedundantDirectedConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
    }
}
